package br.uece.comp.paa.entity.beb;

import br.uece.comp.paa.entity.Varredura;
import br.uece.comp.paa.entity.grafo.Grafo;
import br.uece.comp.paa.entity.param.Solucao;

/**
 * Implementação de Solução baseado em Branch & Bound para encontrar uma árvore
 * Geradora Mínima. Por esta solução, os galhos serão podados por dois
 * critérios: Otimalidade: Quando já é conhecida uma solução de custo menor ou
 * Inviabilidade: Quando a adição da aresta resultou em um ciclo.
 * 
 * @author juliano
 * 
 */
public class BranchAndBound extends Varredura {

	private Solucao melhor;

	public BranchAndBound(Grafo g) {
		super(g);
		melhor = new Solucao(0);
		melhor.setCusto(Double.MAX_VALUE);
	}

	@Override
	public Grafo gerar(Grafo g, int grauMaximo, double custoMaximo) {
		inicializarAtributos(g);
		Solucao solucao;
		Double custo = 0d;
		int[] arraySolucao;

		int count = 0;

		while (gerador.temProxima() && continuar) {
			System.out.println("Avaliando solução " + ++count);

			solucao = gerador.proxima();
			arraySolucao = solucao.getArray();

			for (int i = 0; i < arraySolucao.length; i++) {
				custo = avaliar(grauMaximo, arraySolucao, i, custo);

				if (custo == null || custo > melhor.getCusto()) {
					custo = 0d;
					gerador.setProxima(i);
					break;
				}
			}

			if (custo > 0 && custo < melhor.getCusto()) {
				solucao.setCusto(custo);
				melhor = solucao;
			}
			custo = 0d;
		}

		return getGrafo().extrairArvore(obterListaArestas(melhor));
	}
}
